package two.chapter_2.c2_1;

/**
 * 插入排序： 第一趟，前两个元素相互比较，若<则交换。此时前两个元素是有序的
 *           第二趟，前三个元素相互比较，若<则交换。此时前三个元素是有序的。
 *           第三趟，前四个元素比较，若<则交换。此时前四个元素是有序的。
 *
 *
 * 适用于部分有序数组
 * @param <Item>
 */
public class InsertionSort<Item extends Comparable<Item>> extends Sortable<Item> {

    /**
     * 增长数量级  最坏情况 比较次数 1+2+...N-1=n(n-1)/2  ~n^2/2
     *                    交换次数 1+2+...N-1=n(n-1)/2  ~n^2/2
     *            最好的情况  比较次数 1+1+...+1  （n-1)个1相加 =n-1次
     *                       交换次数  0次
     *
     *            平均情况    比较次数   ~n^2/4
     *                       交换次数   ~n^2/4
     * @param items
     */
    @Override
    public void sort(Item[] items) {

        for (int i=1;i<items.length;i++){
            for (int j=i;j>0 && less(items[j],items[j-1]);j--){//一旦less方法返回false,就不再执行本层for循环
                exch(j-1,j,items);
            }
        }
    }
}
